package a1sort.a5countsort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author zhangMr
 * @description
 * 计数排序-参考算法导论第八章第二小节
 * 运行时间Θ(n)
 */
public class CountSort {
    public static int[] countSort(int[] arr){
        int max=0;
        for(int i=0;i<arr.length;i++){
            max=Math.max(max,arr[i]);
        }
        int[]count=new int[max+1];
        for(int i=0;i<arr.length;i++){
            count[arr[i]]++;
        }
        int[] result=new int[arr.length];
        int index=0;
        for(int i=0;i<count.length;i++){
            if(count[i]>0){
                for(int k=0;k<count[i];k++){
                    result[index++]=i;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Random random=new Random();
        int[]data=new int[10];
        for(int i=0;i<10;i++){
            data[i]= random.nextInt(100);
        }
        System.out.println("随机生成的数组"+ Arrays.toString(data));
        int[] result=countSort(data);
        System.out.println("排序后的数组"+Arrays.toString(result));
    }
}
